Communication systems extensively employ digital signal processing techniques to accomplish increasingly more sophisticated and complex computational algorithms. Expanding applications are being fueled by new technologies and increasing demand for products and services. The Discrete Fourier Transform (DFT) is employed in many of these applications to provide a needed transformation between sampled time-domain signals (that are usually digitized) and their frequency-domain equivalents. The DFT may be calculated in three different ways. A set of simultaneous equations can be employed, but this technique is too inefficient to be of practical use. Correlation techniques can also be used, but computational requirements make this technique cumbersome or expensive to implement on a broad scale.
The Fast Fourier Transform (FFT) is an ingenious algorithm first discovered by Karl Friedrich Gauss, the great German mathematician of a century ago, and rediscovered and applied by J. W. Cooley and J. W. Tukey in 1965. The FFT is typically hundreds of times faster than the other DFT methods mentioned above and is therefore the algorithm of choice for a broad spectrum of applications employing the DFT. For example, the FFT is a critical element of a digital communication system that employs Orthogonal Frequency Division Multiplexing (OFDM) or Discrete Multitone (DMT) techniques.
The FFT is based on a “divide and conquer” model that decomposes a DFT into N points, which actually correspond to N separate DFTs consisting of a single point. The whole transform is then obtained from these simpler transforms. For example, an N-point DFT computation can be divided into two N/2-point DFT computations that can be further divided into two N/4-point DFT computations, and so on until complete. Actually, the division occurs after a reorganization of the points, such that each point corresponds to a two-point DFT in each position when using a method based on radix-2. After this division and DFT computation, a merging process is performed in which the simpler DFT transforms are reassembled into the complete DFT transform. Of course, the Inverse Fast Fourier Transform (IFFT) also advantageously appropriates these techniques to provide transformation between frequency domain data and time domain data.
An input of N real data values may be processed by an N point FFT to provide an output of N complex data values. Conversely, an input of N complex data values may be processed by an N point IFFT to provide an output of N real data values. A basic computational element that is advantageously employed to further enhance the benefits of FFT/IFFT processing is called a butterfly structure. The butterfly structure accepts two complex input numbers and performs one complex multiplication, one complex addition and one complex subtraction to produce two complex output numbers. However, as N increases in magnitude, the number of complex multiplications required increases nonlinearily thereby placing additional burdens on processing and storage requirements.
Accordingly, what is needed in the art is a more effective way to provide N point FFT/IFFT computations employing real data.